# -*- coding: UTF-8 -*-
from typing import List


class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

    # 用来打印debug信息的辅助函数
    def __str__(self):
        str = []
        node = self
        while True:
            str.append(node.val)
            node = node.next
            if node is None:
                break

        return str.__str__()


# 用于将输入List转化为ListNode表示的链表结果
def array_to_list(values) -> ListNode:
    array_length: int = len(values)
    if array_length == 0:
        return None

    node = ListNode(val=values[0])
    temp_node = node
    for index in range(1, array_length):
        new_node = ListNode(val=values[index], next=None)
        temp_node.next = new_node
        temp_node = new_node

    return node


# 将listNode表示的链表转化为Array
def list_to_array(list_node: ListNode) -> []:
    res = []
    while list_node:
        res.append(list_node.val)
        list_node = list_node.next
    return res


class TestcaseHelper:
    @staticmethod
    def print_case(pass_result, case_definition, exec_result, only_print_fail=True):
        input_len = len(case_definition)

        if pass_result:
            if not only_print_fail:
                print('---------------------------')
                print('CASE RESULT: PASS')
                for i in range(0, input_len - 1):
                    case_item = case_definition[i]
                    print('INPUT %d' % (i+1))
                    print(case_item)
                print('---------------------------')
        else:
            print('---------------------------')
            print('CASE RESULT: FAIL')
            for i in range(0, input_len - 1):
                case_item = case_definition[i]
                print('INPUT %d' % (i+1))
                print(case_item)
            print('EXPECT RESULT:')
            print(case_definition[input_len - 1])
            print('WE GET:')
            print(exec_result)
            print('---------------------------\n')


class Stack:
    def __init__(self):
        self.data = []

    def push(self, item):
        self.data.append(item)

    def pop(self):
        if self.is_empty():
            return None
        else:
            return self.data.pop()

    def size(self):
        return len(self.data)

    def is_empty(self):
        return self.size() == 0

    def top(self):
        if self.is_empty():
            return None
        else:
            return self.data[-1]

    def get_data_list(self):
        return self.data

    def add_tail(self, item):
        self.data.insert(0, item)

    def remove_all(self):
        self.data = []


class SolutionBase:
    # 检查结果是否正确的方法，不同的case，检查方法不同
    def check_result(self, expect, result) -> bool:
        return expect == result

    def check_result_array(self, expect, result) -> bool:
        # 检查结果是否正确的方法，不同的case，检查方法不同
        res = True
        if len(expect) == len(result):
            for item in result:
                if not (item in expect):
                    res = False
                    break
            return res
        else:
            return False


def binary_search_right(nums: List[int], target: int) -> int:
    left = 0
    right = len(nums) - 1

    while left <= right:
        mid = left + (right - left) // 2
        mid_value = nums[mid]

        if target == mid_value:
            left = mid + 1
        elif target < mid_value:
            right = mid - 1
        else:
            left = mid + 1

    return left


def binary_search(nums: List[int], target: int) -> int:
    left = 0
    right = len(nums) - 1

    while left <= right:
        mid = left + (right - left) // 2
        mid_value = nums[mid]
        if target == mid_value:
            return mid
        elif target < mid_value:
            right = mid - 1
        else:
            left = mid + 1

    return -1
